package num;

import java.util.Scanner;

/**
 * @program: data_structures_algorithms
 * @description: 获取最大公约数
 * @author: lld
 * @create: 2020-11-14 19:18
 **/
public class GreatestCommonDivisor {
    public static void main(String[] args) {
        System.out.println("请输入两个整数：(用空格隔开)");
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int a = Integer.parseInt(s.split(" ")[0]);
        int b = Integer.parseInt(s.split(" ")[1]);
        System.out.println(getGreatestCommonDivisor(a, b));
    }

    /**
     * @Description: 欧几里得算法
     * * 这条算法基于一个定理：两个正整数a和b（a>b），它们的最大公约数等于a除 以b的余数c和b之间的最大公约数。
     * @Param: [a, b]
     * @return: int
     **/
    public static int getGreatestCommonDivisor(int a, int b) {
        int small = Math.min(a, b);
        int big = Math.max(a, b);
        if (big % small == 0) {
            return small;
        }
        return getGreatestCommonDivisor(big % small, small);
    }
}
